package sf.j2tree.tree;

import java.util.LinkedList;

/**
 * Created by ping on 2017-09-12.
 */
public class BinarySearchTree<T extends Comparable> implements Tree<T> {

    //根结点
    protected BinaryNode<T> root;

    @Override
    public boolean isEmpty() {
        return root == null ? true : false;
    }

    @Override
    public int height() {
        return height(root);
    }

    private int height(BinaryNode node) {
        int height = 0;
        int leftHeight = 0;
        int rightHeight = 0;
        if (node == null) {
            return height;
        }
        height++;
        if (node.left != null) {
            leftHeight += height(node.left);
        }
        if (node.right != null) {
            rightHeight += height(node.right);
        }
        return leftHeight >= rightHeight ? leftHeight : rightHeight;
    }

    @Override
    public int size() {
        return size(root);
    }

    private int size(BinaryNode node) {
        int size = 0;
        if (node == null) {
            return size;
        }
        size++;
        if (node.left != null) {
            size += size(node.left);
        }
        if (node.right != null) {
            size += size(node.right);
        }
        return size;
    }

    @Override
    public String preOrder() {
        return preOrder(root);
    }

    private String preOrder(BinaryNode node) {
        if (node == null) {
            return null;
        }
        StringBuffer sb = new StringBuffer();
        sb.append(node.data).append(",");
        if (node.left != null) {
            sb.append(preOrder(node.left));
        }
        if (node.right != null) {
            sb.append(preOrder(node.right));
        }
        return sb.toString();
    }


    @Override
    public String inOrder() {
        return inOrder(root);
    }

    private String inOrder(BinaryNode node) {
        if (node == null) {
            return null;
        }
        StringBuffer sb = new StringBuffer();
        if (node.left != null) {
            sb.append(inOrder(node.left));
        }
        sb.append(node.data).append(",");
        if (node.right != null) {
            sb.append(inOrder(node.right));
        }
        return sb.toString();
    }

    @Override
    public String postOrder() {
        return postOrder(root);
    }

    private String postOrder(BinaryNode node) {
        if (node == null) {
            return null;
        }
        StringBuffer sb = new StringBuffer();
        if (node.left != null) {
            sb.append(postOrder(node.left));
        }
        if (node.right != null) {
            sb.append(postOrder(node.right));
        }
        sb.append(node.data).append(",");
        return sb.toString();
    }

    @Override
    public String levelOrder() {
        LinkedList<BinaryNode> queue = new LinkedList<>();
        queue.addFirst(root);
        return levelOrder(queue);
    }

    public String levelOrder(LinkedList<BinaryNode> queue) {
        BinaryNode node;
        StringBuffer sb = new StringBuffer();
        while ((node = queue.removeLast()) != null) {
            sb.append(node.data).append(",");
            if (node.left != null) {
                queue.addFirst(node.left);
            }
            if (node.right != null) {
                queue.addFirst(node.right);
            }
        }
        sb.append(levelOrder(queue));
        return sb.toString();
    }

    @Override
    public void insert(T t) {
        if (t == null) {
            throw new IllegalArgumentException("节点不能为空");
        }
        insert(t, root);
    }

    private BinaryNode insert(T t, BinaryNode node) {
        if (node == null) {
            node = new BinaryNode(t);
        } else {
            int result = node.data.compareTo(t);
            if (result > 0) {
                node.left = insert(t, node.left);
            } else if (result < 0) {
                node.right = insert(t, node.right);
            }
        }
        return node;
    }

    @Override
    public void remove(T t) {
        if (t == null) {
            throw new IllegalArgumentException("节点不能为空");
        }
    }

    private BinaryNode remove(T t, BinaryNode node) {
        if (node == null) {
            return null;
        }
        int result = t.compareTo(node.data);
        if (result > 0) {
            node.right = remove(t, node.right);
        } else if (result < 0) {
            node.left = remove(t, node.left);
        } else {
            if (node.left != null && node.right != null) {
                node.data = findMin(node.right).data;
                node.right = remove((T) node.data, node.right);
            } else {
                node = (node.left != null) ? node.left : node.right;
            }
        }
        return node;
    }

    @Override
    public T findMin() {
        return null;
    }

    public BinaryNode findMin(BinaryNode node) {
        return null;
    }

    @Override
    public T findMax() {
        return null;
    }

    @Override
    public BinaryNode findNode(T t) {
        return null;
    }

    @Override
    public boolean contains(T data) throws Exception {
        return false;
    }

    @Override
    public void clear() {

    }
}
